package ShortestPath_F;

import Graph.AdMatrix.GraphKind;
import Graph.AdMatrix.MGraph;

public class ShortestPathmain {
    private static final int INFINITY = Integer.MAX_VALUE;
    public static void main(String[] args) throws Exception {
        Object vex1[] = {"A", "B", "C", "D", "E", "F", "G", "H", "I", "J"};
        int[][] arcs1 = {{0, INFINITY, INFINITY, 3, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY},
                {INFINITY, 0, 4, INFINITY, INFINITY, INFINITY, INFINITY, 5, INFINITY, INFINITY},
                {INFINITY, 4, 0, INFINITY, 6, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY},
                {3, INFINITY, INFINITY, 0, INFINITY, INFINITY, 2, INFINITY, INFINITY, INFINITY},
                {INFINITY, INFINITY, 6, INFINITY, 0, 1, INFINITY, INFINITY, INFINITY, INFINITY},
                {INFINITY, INFINITY, INFINITY, INFINITY, 1, 0, INFINITY, INFINITY, INFINITY, INFINITY},
                {INFINITY, INFINITY, INFINITY, 2, INFINITY, INFINITY, 0, 7, 8, 9},
                {INFINITY, 5, INFINITY, INFINITY, INFINITY, INFINITY, 7, 0, INFINITY, INFINITY},
                {INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, 8, INFINITY, 0, INFINITY},
                {INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, 9, INFINITY, INFINITY, 0},

        };
        MGraph G = new MGraph(GraphKind.UDN, 10, 9, vex1, arcs1);
        ShortestPath_FLOYD floyd = new ShortestPath_FLOYD();
        floyd.FLOYD(G);
        display(floyd.getD());
        findPlace(G, floyd.getD());
    }
    public static void display(int[][] D) {
        System.out.println("各城市之间的最短路径为： ");
        for (int v = 0; v < D.length; v++) {
            for (int w = 0; w < D.length; w++)
                System.out.print(D[v][w] + "\t");
            System.out.println();
        }
    }

    public static void findPlace(MGraph G, int[][] D) throws Exception {
        int min = INFINITY;
        int sum = 0;
        int u = -1;
        for (int v = 0; v < D.length; v++) {
            sum = 0;
            for (int w = 0; w < D.length; w++)
                sum += D[v][w];
            if (min > sum) {
                min = sum;
                u = v;
            }
        }
        System.out.println();
        System.out.println("维修中心应设在" + G.getVex(u) + "处，到其余各城市的路径长度为：");
        for (int i = 0; i < D.length; i++)
            System.out.print(D[u][i] + "\t");
        System.out.println();
    }
}
